class Solution(object):
    def fib(self, n):
        f = [0, 1]
        for i in range(2, n+1):
            f.append(f[i - 1] + f[i - 2])
        print(f)
        return f[n]

print(Solution().fib(10))


class Solution:
    def fib1(self, n: int) -> int:
        if n <= 1:
            return n

        dp = [0, 1]

        for i in range(2, n + 1):
            total = dp[0] + dp[1]
            dp[0] = dp[1]
            dp[1] = total

        return dp[1]
print(Solution().fib1(10))
